package leetcode;

public class BinaryTreeZigzagLevelOrderTraversal103 {
    class ArrayDeque<E> {
        E[] arr;
        int head;
        int tail;

        public ArrayDeque(int capacity) {
            arr = (E[]) new Object[capacity + 1];
        }

        public boolean isEmpty() {
            return head == tail;
        }

        public boolean isFull() {
            return (tail - head + arr.length) % arr.length == arr.length - 1;
        }

        private int inCre(int num) {
            if (num+1 >= arr.length) {
                return 0;
            }
            return num+1;
        }

        public int deCre(int num) {
            if (num-1 < 0) {
                return arr.length - 1;
            }
            return num-1;
        }

        public boolean offerFirst(E val) {
            if (isFull()) {
                return false;
            }
            head = deCre(head);
            arr[head] = val;
            return true;
        }

        public boolean offerLast(E val) {
            if (isFull()) {
                return false;
            }
            arr[tail] = val;
            tail = inCre(tail);
            return true;
        }

        public E pollFirst() {
            if (isEmpty()) {
                return null;
            }
            E val = arr[head];
            arr[head] = null;
            head = inCre(head);
            return val;
        }

        public E pollLast(){
            if(isEmpty()) {
            return null;
            }
            tail = deCre(tail);
            E val = arr[tail];
            arr[tail] = null;
            return val;
        }

        public E peekFirst(){
            if(isEmpty()){
                return null;
            }
            return arr[head];
        }

        public E peekLast(){
            if(isEmpty()){
                return null;
            }
            return arr[deCre(tail)];
        }
    }
}
